package com.haoyang.search;

public class A03_BlockSearchDemo2 {
    public static void main(String[] args) {
        int[] arr = {27, 22, 30, 40, 36, 13, 19, 16, 20, 7, 10, 43, 50, 48};

        Block2 b1 = new Block2(22, 40, 0, 4);
        Block2 b2 = new Block2(13, 20, 5, 8);
        Block2 b3 = new Block2(7, 10, 9, 10);
        Block2 b4 = new Block2(43, 50, 11, 13);

        Block2[] blockArr = {b1, b2, b3, b4};

        int targetNumber = 22;

        int index = getIndex(arr, blockArr, targetNumber);

        System.out.println(index);
    }

    /**
     * 分块查找
     *
     * @param arr
     * @param blockArr
     * @param targetNumber
     */
    private static int getIndex(int[] arr, Block2[] blockArr, int targetNumber) {
        int index = findIndex(blockArr, targetNumber);
        if (index == -1) {
            // 目标数字不在数组中
            return -1;
        }
        int startIndex = blockArr[index].getStartIndex();
        int endIndex = blockArr[index].getEndIndex();
        for (int i = startIndex; i <= endIndex; i++) {
            if (arr[i] == targetNumber)
                return i;

        }
        return -1;
    }

    /**
     * 定义方法寻找目标数字在哪一个块中
     */
    private static int findIndex(Block2[] blockArr, int targetNumber) {
        for (int i = 0; i < blockArr.length; i++) {
            if (targetNumber >= blockArr[i].getMin() && targetNumber <= blockArr[i].getMax()) {
                return i;
            }
        }
        return -1;
    }
}

class Block2 {
    private int min;
    private int max;
    private int startIndex;
    private int endIndex;

    public Block2() {
    }

    public Block2(int min, int max, int startIndex, int endIndex) {
        this.min = min;
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMin() {
        return min;
    }

    public void setMin(int min) {
        this.min = min;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }

    @Override
    public String toString() {
        return "Block{" +
                "min=" + min +
                ", max=" + max +
                ", startIndex=" + startIndex +
                ", endIndex=" + endIndex +
                '}';
    }
}